The present invention relates to high speed computers utilizing virtual memory and, in particular, to methods for implementing virtual memory in a computer system.
Computer systems typically employ a hierarchy of memory devices to accommodate the often conflicting objectives of high speed and low cost. Specifically, a computer typically includes a relatively small main memory unit which comprises comparatively expensive high speed devices, augmented by a larger number of slower, but less expensive secondary memory drives such as rotating disk or magnetic tape storage. The main memory can be directly accessed by the system hardware; the secondary memory, however, is typically accessed through a software operating system. Transfers between main memory and secondary memory are made by the operating system as required.
A virtual memory system is a mechanism for supporting efficient management of the physical memory in a computer system. In such a system a conceptual "virtual memory" is referenced by computer programs to access data and instructions; a "virtual" or "logical" address is employed to denominate an abstract virtual memory location rather than a specific location in the physical memory. The computer system then dynamically correlates (maps) blocks of virtual addresses (typically referred to as "pages" of virtual memory) to correlative blocks (pages) of physical memory locations; at any given time, a mapping of virtual memory pages into physical memory pages is maintained in a table customarily referred to as a page table. A particular page of virtual memory may correlate to a specific page of main memory, or may instead be resident in secondary memory.
Under the control of the computer's operating system, the mapping of virtual to physical pages (and, consequently, the contents of the page tables) changes in accordance with demand. As a program executes its defined steps, instructions accessing memory refer to virtual memory locations. Computer hardware then, in conjunction with the page table, translates the virtual address to an actual physical address. If it is determined that the virtual address does not correspond to a location in the main memory, the hardware triggers a program trap (typically referred to as a page fault), stores indicia of the state of the processor at the time the instruction causing the page fault began execution, and relinquishes control to the operating system software. The operating system then accesses the page in secondary memory corresponding to the virtual memory page containing the referenced virtual address and transfers it into main memory. If necessary, the contents of another page of physical memory is transferred to secondary memory to accommodate entry of the new virtual page. The operating system the modifies the page tables to reflect the change, restores the processor values to the pre-trap state and passes control back to the original program. The original program can then access the desired virtual memory location and proceed with the program execution.
To facilitate direct processing of the page table by the processor hardware, prior art systems conventionally utilize hardware designed to implement a particular structure. This results in inflexibility of the design of page tables and requires that system's software to be adapted to the specific hardware table structure. In addition, page table structures tend to be particularly rigid in order to reduce hardware control complexity. More complex and flexible hardware page table structures that would accommodate variations in software are typically not used.
Retention of a number of recent virtual page to physical page translations in a processor buffer to facilitate address translation is, in general, known. Such a buffer is often referred to as a "translation look aside buffer." When a virtual to physical translation is required, the hardware first checks entries held in the buffer. If the desired mapping is present in the translation look aside buffer, the physical address is immediately available for use. Otherwise, the hardware consults the page tables in memory, and places an entry describing the most recent address translation into the translation look aside buffer for future reference. In the process, an older translation look aside buffer entry may be discarded.
The use of such a translation look aside buffer, however, is disadvantageous in a highly parallel computer system. Processor state values must be retained until it is determined that a page fault will not occur. That time period is unpredictable; translation of a virtual address in the translation look aside buffer is done quickly and within a predictable time, whereas translations in which the hardware must refer to the page tables take more time. Saving and restoring processor values is therefore complicated.